package leetcode.daily;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

public class a_20201221 {

    /**
     *
     * 1104. 二叉树寻路
     * 在一棵无限的二叉树上，每个节点都有两个子节点，树中的节点 逐行 依次按 “之” 字形进行标记。
     *
     * 如下图所示，在奇数行（即，第一行、第三行、第五行……）中，按从左到右的顺序进行标记；
     *
     * 而偶数行（即，第二行、第四行、第六行……）中，按从右到左的顺序进行标记。
     *
     *
     *
     * 给你树上某一个节点的标号 label，请你返回从根节点到该标号为 label 节点的路径，该路径是由途经的节点标号所组成的。
     *
     *
     *
     * 示例 1：
     *
     * 输入：label = 14
     * 输出：[1,3,4,14]
     * 示例 2：
     *
     * 输入：label = 26
     * 输出：[1,2,6,10,26]
     *
     *
     * 提示：
     *
     * 1 <= label <= 10^6
     *
     */
    public static List<Integer> pathInZigZagTree(int label) {
        List<Integer> result = new ArrayList<>();
        // 按正常顺序排列的话 label 的父节点是 label>>1
        // 求出正常排列的父节点label 然后求label所在行数 row = label-%2开平方 实际节点就等于 if（row%2 == 0) l = rowENd-label+rowStart
        if(label == 1){
            result.add(1);
            return result;
        }
        int row = (int)(Math.log(label)/Math.log(2)); // 利用对数的性质 求 2的对数
        int rowStart = (int)Math.pow(2, row);
        int rowEnd = 2*rowStart-1;
        int curr = label;
        for(int r = row; r >= 0; r--){
            result.add(curr);
            curr = rowEnd-curr+rowStart;
            curr >>= 1;
            rowEnd = rowStart-1;
            rowStart = rowStart/2;
        }
        Collections.reverse(result);
        return result;
    }


    /**
     * 1108. IP 地址无效化
     * 给你一个有效的 IPv4 地址 address，返回这个 IP 地址的无效化版本。
     *
     * 所谓无效化 IP 地址，其实就是用 "[.]" 代替了每个 "."。
     *
     *
     *
     * 示例 1：
     *
     * 输入：address = "1.1.1.1"
     * 输出："1[.]1[.]1[.]1"
     * 示例 2：
     *
     * 输入：address = "255.100.50.0"
     * 输出："255[.]100[.]50[.]0"
     *
     *
     * 提示：
     *
     * 给出的 address 是一个有效的 IPv4 地址
     */
    public String defangIPaddr(String address) {
        return address.replaceAll("\\.", "[.]");
    }

    public static void main(String[] args){
        System.out.println(pathInZigZagTree(26));
    }
}
